MAYBE
* Step 1: Failure MAYBE
  + Considered Problem:
      - Strict TRS:
          assoc#2(x2,Nil()) -> bot[0]#1()
          assoc#2(x8,Cons(Pair(x6,x4),x2)) -> ite#3(eqNat#2(x6,x8),x4,assoc#2(x8,x2))
          aux#2(x40,Nil()) -> x40
          aux#2(x6,Cons(x4,x2)) -> aux#2(Cons(x4,x6),x2)
          concat#2(Cons(x6,x4),x2) -> Cons(x6,concat#2(x4,x2))
          concat#2(Nil(),x44) -> x44
          eqNat#2(0(),0()) -> True()
          eqNat#2(0(),S(x20)) -> False()
          eqNat#2(S(x20),0()) -> False()
          eqNat#2(S(x4),S(x2)) -> eqNat#2(x4,x2)
          eval#2(x4,Not(x2)) -> lnot#1(eval#2(x4,x2))
          eval#2(x4,Var(x2)) -> assoc#2(x2,x4)
          eval#2(x6,And(x4,x2)) -> land#2(eval#2(x6,x4),eval#2(x6,x2))
          eval#2(x6,Or(x4,x2)) -> lor#2(eval#2(x6,x4),eval#2(x6,x2))
          ite#3(False(),x40,x48) -> x48
          ite#3(True(),x40,x48) -> x40
          land#2(False(),x28) -> False()
          land#2(True(),x28) -> x28
          lnot#1(False()) -> True()
          lnot#1(True()) -> False()
          lor#2(False(),x32) -> x32
          lor#2(True(),x32) -> True()
          main(x3,x2,x1) -> table_make#3(x2,x1,x3)
          table_make#3(x4,Cons(x3,x2),x1) -> concat#2(table_make#3(Cons(Pair(x3,True()),x4),x2,x1)
                                                     ,table_make#3(Cons(Pair(x3,False()),x4),x2,x1))
          table_make#3(x4,Nil(),x6) -> Cons(Pair(aux#2(Nil(),x4),eval#2(x4,x6)),Nil())
      - Signature:
          {assoc#2/2,aux#2/2,concat#2/2,eqNat#2/2,eval#2/2,ite#3/3,land#2/2,lnot#1/1,lor#2/2,main/3
          ,table_make#3/3} / {0/0,And/2,Cons/2,False/0,Nil/0,Not/1,Or/2,Pair/2,S/1,True/0,Var/1,bot[0]#1/0}
      - Obligation:
          innermost runtime complexity wrt. defined symbols {assoc#2,aux#2,concat#2,eqNat#2,eval#2,ite#3,land#2,lnot#1
          ,lor#2,main,table_make#3} and constructors {0,And,Cons,False,Nil,Not,Or,Pair,S,True,Var,bot[0]#1}
  + Applied Processor:
      EmptyProcessor
  + Details:
      The problem is still open.
MAYBE